package com.gitee.ywj1352.leecode;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author wenjie.yang on 2019/10/5.
 */
public class FenZhi {

    /**
     * [
     * [2],
     * [3,4],
     * [6,5,7],
     * [4,1,8,3]
     * ]
     */
    public int minimumTotal(List<List<Integer>> triangle) {

        int s1 = triangle.size();
        int s2 = triangle.get(s1 - 1).size();
        int[][] arr = new int[s1][s2];
        arr[0][0] = triangle.get(0).get(0);
        if (s1 == 0) {
            return 0;
        }
        if (s1 == 1) {
            return arr[0][0];
        }
        for (int i = 1; i < s1; i++) {
            int size = triangle.get(i).size();
            for (int j = 0; j < size; j++) {
                if (j == 0) {
                    arr[i][j] = arr[i - 1][j] + triangle.get(i).get(j);
                } else if (j == size - 1) {
                    arr[i][j] = arr[i - 1][j - 1] + triangle.get(i).get(j);
                } else {
                    arr[i][j] = Math.min(arr[i - 1][j], arr[i - 1][j - 1]) + triangle.get(i).get(j);
                }
            }
        }
        int[] ints = arr[triangle.size() - 1];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < ints.length; i++) {
            if (min > ints[i]) {
                min = ints[i];
            }
        }
        return min;
    }

    @Test
    public void minimumTotal() {
        List<List<Integer>> lists = Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3));
        int i = minimumTotal(lists);
        System.out.println(i);
    }


}
